// 1646. 获取生成数组中的最大值
// 模拟法

#include <vector>
using namespace std;

class Solution 
{
public:
    int getMaximumGenerated(int n) 
    {
        if(0 == n) return 0;

        vector<int> nums(n + 1);
        nums[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
        }

        int max = 0;
        for(int i = 0; i <= n; i++) if(nums[i] > max) max = nums[i];

        return max;
    }
};